package codeTop;

public class q5 {
    //动态规划
    public String longestPalindrome1(String s) {
        if (s==null || s.isEmpty()) return "";
        boolean[][] dp = new boolean[s.length()+1][s.length()+1];
        for (int i = 0; i <= s.length(); i++) {
            dp[i][i] = true;
        }
        for (int i = 1; i <= s.length(); i++) {
            dp[i-1][i] = true;
        }
        int max = 1;
        String longest = s.substring(0,1);
        for (int i = 2; i <=s.length() ; i++) {
            for (int j = 0;j<=i-2;j++){
                dp[j][i] = dp[j+1][i-1] && (s.charAt(j)==s.charAt(i-1));
                if (dp[j][i]&&i-j>max){
                    max = i-j;
                    longest = s.substring(j,i);
                }
            }
        }
        return longest;
    }
    //中心扩展
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";
        int max = 1;
        String longest = s.substring(0,1);
        for (int i = 1; i <s.length() ; i++) {
            if (s.charAt(i)==s.charAt(i-1)) {
                int len = 0;
                while (i+len+1<s.length() && i-1-len-1>=0&&s.charAt(i+len+1)==s.charAt(i-1-len-1)) {
                    len++;
                }
                if (len * 2 + 2 > max) {
                    max = len * 2 + 2;
                    longest = s.substring(i-len-1,i+len+1);
                }
            }
            int len = 0;
            while (i+len+1<s.length()&&i-len-1>=0&&s.charAt(i+len+1)==s.charAt(i-len-1)) {
                len++;
            }
            if (len * 2 + 1 > max) {
                max = len * 2 + 1;
                longest = s.substring(i-len,i+len+1);
            }

        }
        return longest;
    }

    public static void main(String[] args) {
        q5 q5 = new q5();
        System.out.println(q5.longestPalindrome("abcba"));
    }
}
